User blog:DontDrinkH20/"Interesting numbers" and the 3 Classes of Googolisms
= Type A, Type B, and Type C Googolisms = There are really three types of googolisms. There are those which are very very large but have many equivalent definitions, like TREE(3) and Graham's number, and there are others which are very very large but are defined in such a way that they don't have many equivalent definitions, such as Rayo's number, BIG FOOT, and the current largest valid googolism, Little Bigeddon. Type A and Type C The first type of googolisms mentioned above is what I like to call Type A, the second Type C. Type A objects are abundant on the wiki, by far the most often-made googolism. There are really only a few Type C googolisms (about 4 well-known ones). Type A has numbers like googolplex and Graham's number as well as functions like BEAF and FGH. Type A objects generally contain definitions of exponentiation and many nested recursive definitions. Type A googolisms can be thought of as the ones which can easily be defined in PA and where it is easy to see that they would make a very large number. Type C googolisms on the other hand are quite scarce, although they may hold a lot of potential. Examples of Type C are Rayo's number, BIG FOOT, and the current largest valid googolism, Little Bigeddon. They typically include creating very expressive languages, and then defining numbers as "very difficult to express in those languages." There are only about 4 well-known ones. Type C googolisms can be thought of ones which are defined as being difficult to define with a certain amount of expressiveness. The Elusive Type B Type A is actually a bit smaller than I originally may have led you to believe, although the wiki is still mostly populated by these objects. Type A must contain objects where it is easy to see that they would produce very large numbers, typically involving repeated exponentiation and incredibly deep nested recursions. These googolisms often share equivalent values. An example of a Type B googolism is TREE(3). However, the largest valid Type B googolism is not TREE(3). It is called SCG(n), standing for the "subcubic graph number" of n. Although it is incidentally faster growing than every single function which is provably total in a primitive theory, it is still well-defined in finitary ZF and therefore is well-defined in PA (PA and finitary ZF are mutually interpretable). There is no obvious reason why Type B googolisms would be large at all. TREE(3) revolves around a simple game, and it seems very odd that it would create such large numbers out of practically nothing. The idea behind Type B googolisms is that they don't relate to exponentiation or recursion in any major way but still somehow manage to be googolisms. Here are some examples: *TREE(n) *SCG(n), the subcubic graph number of n *The busy beaver function, \(\Sigma(n)\) *The Hydra function As can be seen by the Busy Beaver function, there are some Type B googolisms which do have some intuition on why they would be large. The reason they are still not Type A is that they have little to no recursion in their definition that would make them large. Type B is truly the most elusive type of googolisms, regardless of the fact that there are more Type B than there are Type C. These numbers inherently have a very interesting property, and yet are out of the question for being expressed in a normal human notation. Yet, because they share so many properties with Type A, they can be grouped together to form a class called PA-friendly googolisms. These are simply the ones which are easy to express in PA or a theory interpreted by PA (like finitary ZF). = Interesting Numbers = Sufficiently large numbers can be thought of as interesting if they can be described in many ways; that is, they have many different definitions. However, the closer \(n\) gets to \(m\), the more formulae there are of size \(n\) which approximate \(m\). For this reason, a number could also be thought of as interesting if it can be described in very concise ways relative to it's own size; that is, there are definitions of the number which are tiny in comparison to the number itself. Examples of this include: *Googolplex *TREE(3) *Graham's number Wait a second... these look a lot like our old friends, the PA-friendly googolisms! Yep! Note that while these functions are examples of such previously described "interesting numbers", this is likely not anywhere close to an equivalence. That's why the "interesting numbers" and PA-friendly googolisms should not be defined to be the same; in fact, the PA-friendly googolisms shouldn't even be defined at all. They are more of an opinion than anything. The interesting part is that there is a correlation, and one of these things is completely subjective, while the other can be formalized. Hey, why don't we do that? Complexity of Formulae There is a famous way to prove that something is true for every formula of a given first-order language: induction on complexity of formulae. This is a method of induction by showing something holds for atomic formulae and then showing that when making a formula more complex in any way, is still holds for that formula. Interestingly, a ranking system of how difficult it is to produce a formula from nothing is created out of this. Formal definition and Proofs The formal definition of the complexity of a formula \(\varphi\) in the language of PA is as follows: *Let \(T_0 = \{\ulcorner 0\urcorner\}\cup\{\ulcorner x_n\urcorner : n\in\omega\} \) *Let \(T_{n+1} = \{\ulcorner S(t)\urcorner, \ulcorner t + u\urcorner, \ulcorner t\cdot u\urcorner : t\in T_a, u\in T_b, a + b = n\}\cup T_n \) *Let \(F_0 = \{\ulcorner a = b\urcorner : a, b\in T_0\} \) *Let \(F_{n+1} = \{\ulcorner a = b\urcorner : a,b\in T_{n+1}\}\) \(\cup\{\ulcorner\neg\varphi\urcorner, \ulcorner\chi\land\psi\urcorner, \ulcorner\chi\lor\psi\urcorner, \ulcorner\forall x_m(\varphi)\urcorner, \ulcorner\exists x_m(\varphi)\urcorner : \varphi\in F_n,\chi\in F_a,\psi\in F_b, a + b = n,m\in\omega\}\) \(\cup F_n\) *Let the complexity of \(\varphi\) be \(\mathcal{C}(\varphi) = \min\{n : \varphi\in F_n\}\) \(F_n\) is a "rank" of formulae. What will be shown is that: *Every formula in the language of PA is in \(F_n\) for some \(n\). *Every formula in \(F_{n+1}\setminus F_n\) has length at least \(n+4\). The first proof will be done with induction on complexity of formulae. *Every number \(n\in\omega\) can be defined in \(\omega\) using a formula of complexity at most \(n\). #Let \(t\) be any term in the language of PA. If \(t\) is a constant symbol or a variable symbol, then by definition \(t\in T_0\). If \(t = \ulcorner S(u)\urcorner\) for a term \(u\in T_n\), then \(t\in T_{n+1}\). Therefore, for any term \(t\) in the language of PA, there is some \(n\) such that \(t\in T_n\) by induction on terms. #Let \(\varphi\) be an atomic formula. Because the only predicate of the language of PA is \(\ulcorner=\urcorner\), \(\varphi\) is of the form \(\ulcorner a = b\urcorner\) for terms \(a\) and \(b\). By 1. these terms are both in \(T_n\) for some two (respective) \(n\). Let \(a\in T_n\) and \(b\in T_m\) where \(k=\max\{n,m\}\). Then, \(\ulcorner a = b\urcorner\in F_k\) and so \(\varphi\in F_k\). #Let \(\varphi\) be \(\ulcorner\neg\psi\urcorner\) where \(\psi\in F_n\). Then \(\varphi\in F_{n+1}\). #Let \(\varphi\) be \(\ulcorner\chi\land\psi\urcorner\) where \(\psi,\chi\in F_n,F_m\). Then \(\varphi\in F_{n+m+1}\). #Let \(\varphi\) be \(\ulcorner\chi\lor\psi\urcorner\) where \(\psi,\chi\in F_n,F_m\). Then \(\varphi\in F_{n+m+1}\). #Let \(\varphi\) be \(\ulcorner\forall x_m(\psi)\urcorner\) where \(\psi\in F_n\). Then \(\varphi\in F_{n+1}\). #Let \(\varphi\) be \(\ulcorner\exists x_m(\psi)\urcorner\) where \(\psi\in F_n\). Then \(\varphi\in F_{n+1}\). The induction on complexity of formulae is complete. So, for every \(\varphi\), there is an \(n\) such that \(\varphi\in n\), and therefore \(\mathcal{C}\) is defined on every \(\varphi\). Next, I will prove by induction on natural numbers that every formula in \(F_{n+1}\setminus F_n\) has length at least \(n+4\). #\(F_1\setminus F_0\) consists of: ##Formulae which are in \(F_0\) but with some added symbols, making each such formula at least 4 symbols long ##Formulae which are \(\ulcorner a = b\urcorner\) where \(a\) and \(b\) are terms exclusively in \(T_1\) (the smallest of those terms are of the form \(S(t)\) where \(t\) is one symbol), meaning such formulae are at least 5 symbols long #Let every formula of \(F_n\setminus F_{n-1}\) have length at least \(n+3\). Then, \(F_{n+1}\setminus F_n\) consists of: ##Formulae which are in \(F_n\setminus F_{n-1}\) but with some added symbols, making each such formula at least \(n+4\) symbols long ##Formulae which are \(\ulcorner a = b\urcorner\) where \(a\) and \(b\) are terms exclusively in \(T_{n+1}\) (the smallest of those terms are of the form \(S^{n+1}(t)\) where \(t\) is one symbol), meaning such formulae are at least \(2n + 3\) symbols long Therefore, every formula in \(F_{n+1}\setminus F_n\) has length at least \(n+4\). This also proves that the length of \(\varphi\) is at least \(\mathcal{C}(\varphi) + 3\). This exercise is trivial and left for the reader. (kek) Finally, I will prove quite easily that every number \(n\in\omega\) can be defined in \(\omega\) using a formula of complexity at most \(n\) using induction on natural numbers. More specifically, I will prove that \(S^n(0) = x\) has complexity at most \(n\): #\(0\) and \(x\) are both in \(T_0\), therefore \(0 = x\) has complexity \(0\) #If \(S^n(0)\) is in \(T_n\), then \(S^{n+1}(0)\) is in \(T_{n+1}\) (therefore \(S^n(0)\) is in \(T_n\) for every \(n\)) #\(S^n(0)\) and \(x\) are both in \(T_n\), therefore \(S^n(0) = x\) has complexity at most \(n\) Complexity and Interest Factor of a Number Finally, we can define what it means for a number to be interesting or difficult to describe in PA. Normally, "the amount of symbols of..." would be used, but I feel like this definition is much more true to the mathematics at hand. Complexity The complexity of a number \(n\) is defined as \(c(n)\min\{\mathcal{C}(\varphi):\omega\models\forall x(\varphix\leftrightarrow x = n)\}\). That is, it is the least complexity of any definition of \(n\). Note that the complexity of \(n\) must be at most \(n\) itself, as shown in the last proof (this is a nice corollary). Let PA(x) be the analog of Rayo(x) for PA rather than FOST. The complexity of PA(x) must be at least \(x-2\) because of the second theorem: #Assume that c(PA(x)) is less than \(x-2\). #There is a formula \(\varphi\) with complexity at most \(x-3\) which defines PA(x). #By definition of PA(x), this formula must have length at least \(x+1\). #By the second theorem, the length of \(\varphi\) is at least \(\mathcal{C}(\varphi) + 3\) which is at most \(x\), and therefore the length of \(\varphi\) is too small to define PA(x). Ahoy, contradiction! Defining an Interesting Number: The Interest Factor Intuitively, one would assume that a number is more "interesting" if it has a lower complexity. After all, then it has very small definitions relative to itself, meaning that there is an interesting property about it that can be easily summed up on a wikipedia page. However, this is false once one considers that simply being summed up easily doesn't automatically make it interesting. For example: Take any \(x\) which is considered interesting. \(x+n\) can be defined with a formula of complexity only \(n+3\) steps over the complexity of \(x\) itself. In other words, \(c(x+n)\leq c(x)+n+3\). Of course, this would imply \(x+n\) to be just about as interesting as \(x\), which is not really true. For example, if TREE(3) has complexity \(n\) (making it interesting, which it is), then the complexity of TREE(3) + 1 is at most \(n+4\), which is really not a big difference considering how uninteresting TREE(3) + 1 is. So rather than studying where \(c(x)\) is low, studying where \(c(x)\) is much lower than before is MUCH more interesting. As such, the definition should be that a number is interesting when \(c(n-k) + k > c(n)\) for most \(k < n\). A number \(n\) is \(a\)-interesting for some \(a\leq n\) when for every \(0c(n)\) and \(c(n+d)+d>c(n)\). The Interest Factor of \(n\) is the largest number \(a\) for which \(n\) is \(a\)-interesting. Intuitively, \(n\) is \(a\)-interesting when \(n\) isn't "mooching" off of the interesting features of \(a\)-many numbers below \(n\). Extra Propositions and Definitions Let \(\mathcal{I}_a\) be the least \(a\)-interesting number. Clearly, every number is \(0\)-interesting by vacuous implication, as there are no numbers \(k\) with \((n - 0)\leq k < n\). Therefore, every number has some interest factor. Therefore \(\mathcal{I}_0=0\). It's also clear that every \(a\)-interesting number is \(b\)-interesting for every \(b0\) is \(1\)-interesting if and only if \(c(n-1) + 1 > c(n)\) and \(c(n+1) + 1 > c(n)\), equivalently \(c(n-1) \geq c(n)\) and \(c(n+1) \geq c(n)\), or even more intuitively if and only if \(c(n)\) is not larger than \(c(n-1)\) or \(c(n+1)\). \(\mathcal{I}_1\) is also the least \(n\) such that \(c(n) < n\) and \(c(n+1) > n - 2\) because: #Let \(n\) be the least \(n\) such that \(c(n) n\). Then \(n\) is \(1\)-interesting because \(c(n-1)=n\) and so \(c(n-1) + 1 = n + 1 > n\) and \(c(n+1) + 2 > n\) so \(c(n+1) + 1 > n -1\geq c(n) \) and \(c(n+1) + 1 > c(n) \). #For any \(k